package problem1027;

//1027.最长等差序列
//https://leetcode.cn/problems/longest-arithmetic-subsequence/

import java.util.HashMap;

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<n; j++) {
                dp[i][j] = 2;
            }
        }
        dp[0][0] = 1;
        int ret = 0;
        HashMap<Integer, Integer> hash = new HashMap<>();
        hash.put(nums[0],0);
        for(int i = 0; i<n; i++) {
            for(int j = i+1; j<n; j++) {
                int x = 2*nums[i] - nums[j];
                if(hash.containsKey(x)) {
                    int k = hash.get(x);
                    dp[i][j] = Math.max(dp[i][j], dp[k][i]+1);
                }
                ret = Math.max(ret, dp[i][j]);
            }
            hash.put(nums[i], i);
        }
        return ret;
    }
}

/*
dp[i][j]: 以第i和第j个数为结尾得最长等差数列的长度 i < j
k i j
x1 x2 x3
x1 - x2 = x2 - x3
x1 = 2*x2-x3;
*/